<!DOCTYPE HTML>
<html>

<head>
	<link rel="bookmark"  type="image/x-icon"  href="/img/logo.jpg"/>
	<link rel="shortcut icon" href="/img/logo.jpg">
	
			    <title>
    北望你的安
    </title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no" />
    <link rel="stylesheet" href="/css/mic_main.css" />
    <link rel="stylesheet" href="/css/dropdownMenu.css" />
    <meta name="keywords" content="北望你的安" />
    
    	<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
	 
    <noscript>
        <link rel="stylesheet" href="/css/noscript.css" />
    </noscript>
    <style type="text/css">
        body:before {
          content: ' ';
          position: fixed;
          top: 0;
          background: url('/img/bg.jpg') center 0 no-repeat;
          right: 0;
          bottom: 0;
          left: 0;
          background-size: cover; 
        }
    </style>

			    
  


    <script src="/js/jquery.min.js"></script>
    <script src="/js/jquery.scrollex.min.js"></script>
    <script src="/js/jquery.scrolly.min.js"></script>
    <script src="/js/skel.min.js"></script>
    <script src="/js/util.js"></script>
    <script src="/js/main.js"></script>
	
</head>
    
		
<!-- Layouts -->



<!--  代码渲染  -->
<link rel="stylesheet" href="/css/prism_coy.css" />
<link rel="stylesheet" href="/css/typo.css" />
<!-- 文章页 -->
<body class="is-loading">
    <!-- Wrapper 外包 s-->
    <div id="wrapper" class="fade-in">
        <!-- Intro 头部显示 s -->
        <!-- Intro 头部显示 e -->
        <!-- Header 头部logo start -->
        <header id="header">
    <a href="/" class="logo">Krystalan</a>
</header>
        <!-- Nav 导航条 start -->
        <nav id="nav" class="special" >
            <ul class="menu links" >
			<!-- Homepage  主页  --> 
			<li >
	            <a href="/" rel="nofollow">主页</a>
	        </li>
			<!-- categories_name  分类   --> 
	        
	        <li class="active">
	            <a href="#s1">分类</a>
	                    <ul class="submenu">
	                        <li>
	                        <a class="category-link" href="/categories/%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0/">强化学习</a></li><li><a class="category-link" href="/categories/%E6%95%B0%E5%AD%A6/">数学</a></li><li><a class="category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></li><li><a class="category-link" href="/categories/%E8%87%AA%E7%84%B6%E8%AF%AD%E8%A8%80%E5%A4%84%E7%90%86/">自然语言处理</a></li><li><a class="category-link" href="/categories/%E9%9A%8F%E7%AC%94/">随笔</a>
	                    </ul>
	        </li>
	        
	        <!-- archives  归档   --> 
	        
	        
		        <!-- Pages 自定义   -->
		        
		        <li>
		            <a href="/tags/" title="标签">
		                标签
		            </a>
		        </li>
		        
		        <li>
		            <a href="/gallery/" title="相册">
		                相册
		            </a>
		        </li>
		        


            </ul>
            <!-- icons 图标   -->
			<ul class="icons">
                    
                    <li>
                        <a title="github" href="https://github.com/krystalan" target="_blank" rel="noopener">
                            <i class="icon fa fa-github"></i>
                        </a>
                    </li>
                    
                    <li>
                        <a title="500px" href="https://www.zhihu.com/people/krystalzhu-an" target="_blank" rel="noopener">
                            <i class="icon fa fa-500px"></i>
                        </a>
                    </li>
                    
			</ul>
</nav>

        <div id="main" >
            <div class ="post_page_title_img" style="height: 25rem;background-image: url(/img/13.jpg);background-position: center; background-repeat:no-repeat; background-size:cover;-moz-background-size:cover;overflow:hidden;" >
                <a href="#" style="padding: 4rem 4rem 2rem 4rem ;"><h2 >强化学习纲要（二） MDP</h2></a>
            </div>
            <!-- Post -->
            <div class="typo" style="padding: 3rem;">
                <blockquote>
<p>视频链接：<br><a href="http://www.bilibili.com/video/BV1g7411m7Ms" target="_blank" rel="noopener">www.bilibili.com/video/BV1g7411m7Ms</a><br><a href="http://www.bilibili.com/video/BV1u7411m7rh" target="_blank" rel="noopener">www.bilibili.com/video/BV1u7411m7rh</a>   </p>
</blockquote>
<h1 id="1-马尔可夫过程"><a href="#1-马尔可夫过程" class="headerlink" title="1.马尔可夫过程"></a>1.马尔可夫过程</h1><p>详见我之前写的另一篇文章：<u><a href="https://wangjiaan.xyz/2020/03/18/StochasticProcess3/" target="_blank" rel="noopener">《随机过程 第4章》</a></u>  </p>
<h1 id="2-马尔可夫奖励过程MRP"><a href="#2-马尔可夫奖励过程MRP" class="headerlink" title="2.马尔可夫奖励过程MRP"></a>2.马尔可夫奖励过程MRP</h1><h2 id="2-1-基本概念"><a href="#2-1-基本概念" class="headerlink" title="2.1 基本概念"></a>2.1 基本概念</h2><p>马尔可夫奖励过程 = 马尔可夫链 + 奖励<br>奖励函数是一个期望，当你到达某个状态的时候，可以获得多大的奖励。<br><img src="/images/RL/8.jpg" alt="MRP"><br>如上图所示（s1状态有5个奖励，s7状态有10个奖励），对于马尔可夫链的每一个状态去定义一个奖励。     </p>
<p>其余概念：<br>（1）Horizon：每个episode里最大的时间步数，可以是无限的，当有限时，整个MRP称为有限马尔可夫（奖励）过程。<br>（2）Return：把每一步的奖励进行折扣，获得总体收益，越往后得到的奖励折扣的越多。<br><img src="/images/RL/9.jpg" alt="RETURN"><br>说明更期望得到现有的奖励，未来得到的奖励就要打折扣。<br>γ为discount factor折价因子。<br>（3）state value function：<br>对于马尔可夫奖励过程定义一个状态价值函数（关于return的期望）<br><img src="/images/RL/10.jpg" alt="状态价值函数"><br>代表从当前的状态开始，有可能获得的价值期望，可以反映出当前状态的好坏。  </p>
<h2 id="2-2-价值计算"><a href="#2-2-价值计算" class="headerlink" title="2.2 价值计算"></a>2.2 价值计算</h2><p>如本节一开始的例子，我们现在来计算s4状态的价值函数。<br>可以通过MC采样过程计算，也可以使用<strong>贝尔曼等式</strong>来计算：<br><img src="/images/RL/11.jpg" alt="贝尔曼等式"><br>基本思路与PageRank相似，通过迭代至参数收敛即可。<br>迭代方法：动态规划、蒙特卡罗、TD learning<br>①来看一下蒙特卡罗方法：<br><img src="/images/RL/13.jpg" alt="蒙特卡罗"><br>简述一下就是：从t时间下的s状态开始，产生N条轨迹，计算这N条轨迹的奖励的平均值，即为s状态下的价值。<br>蒙特卡罗的思想非常简单：就是通过大量采样近似求解，其一个非常经典的应用就是计算积分：在空间上计算积分区域内的采样点占比。<br>②直接迭代计算：当两次迭代中奖励变化小于某阈值时停止迭代，和EM算法类似。  </p>
<p>如果MRP状态少的话，可以把该等式写成矩阵形式，但写成矩阵形式之后，我们无法保证矩阵满秩，所以并不能直接求解，再者矩阵求逆复杂度极高。（故该方法只适用于状态数少的MRP）<br><img src="/images/RL/12.jpg" alt="矩阵形式的MRP">  </p>
<h2 id="2-3-折价因子γ的用处"><a href="#2-3-折价因子γ的用处" class="headerlink" title="2.3 折价因子γ的用处"></a>2.3 折价因子γ的用处</h2><p>（1）避免在有限马尔可夫过程中产生无穷的奖励（有限马尔可夫过程成环）<br>（2）期望得到尽可能快的奖励，比如相比于一周之后得到100块钱，我更期望现在就得到这100块钱。<br>（3）人和动物的行为里面，大家都希望得到立刻奖励。<br>（4）如果γ为0，则只关注当前的奖励；如果γ为1，代表对未来并没有折扣（即未来获得的奖励和当前获得的奖励的价值是一样的）。<br>（5）是强化学习中的超参数。  </p>
<h1 id="3-马尔可夫决策过程MDP"><a href="#3-马尔可夫决策过程MDP" class="headerlink" title="3.马尔可夫决策过程MDP"></a>3.马尔可夫决策过程MDP</h1><h2 id="3-1-基本概念"><a href="#3-1-基本概念" class="headerlink" title="3.1 基本概念"></a>3.1 基本概念</h2><p>MDP = MRP + Decision = MP + Reward + Decision<br><img src="/images/RL/14.jpg" alt="MDP"><br>可以看出，在MDP中，状态转移和奖励函数需要考虑当前时间agent采取的行为（即decision）。<br>所以MDP是由状态集合、行为集合、状态转移、奖励函数、决策函数以及折价因子构成的。  </p>
<p>其中决策函数（Policy）的定义如下：<br><img src="/images/RL/15.jpg" alt="Policy"><br>从当前状态产生行为分布/极大化概率单一行为，同时可以看出它是一个静态的，与时间t无关。  </p>
<h2 id="3-2-MDP与MP-MRP的对比"><a href="#3-2-MDP与MP-MRP的对比" class="headerlink" title="3.2 MDP与MP/MRP的对比"></a>3.2 MDP与MP/MRP的对比</h2><p><img src="/images/RL/16.jpg" alt="对比"><br>（1）就相当于多了一个行为。<br><img src="/images/RL/22.jpg" alt="贝尔曼"><br>（2）MDP不会随波逐流！因为其拥有决策函数</p>
<h2 id="3-3-MDP中的价值函数："><a href="#3-3-MDP中的价值函数：" class="headerlink" title="3.3 MDP中的价值函数："></a>3.3 MDP中的价值函数：</h2><p>首先定义了一个Q函数表示在状态s和行为a下所产生的价值的期望：<br><img src="/images/RL/17.jpg" alt="Q函数"><br>那么原先的价值函数可以改写成：<br><img src="/images/RL/18.jpg" alt="价值函数"><br>就相当于价值函数等于当前状态s的所有行为产生的价值期望。<br>于是我们可以把价值函数和Q函数分别分解成立即奖励与长远奖励（即贝尔曼期望等式）：<br><img src="/images/RL/19.jpg" alt="贝尔曼"><br>先看（7）式，就相当于在s状态下，进行了a行为，然后可以得到下一个状态的概率分布。R(t+1)就是下一个状态的奖励，而在下一个状态下再次利用行为和状态计算下下次奖励的时候需要用到折价因子。<br>再看（6）式，其实就和上述思路一致，只不过没有将行为拆分讨论。  </p>
<p>接着我们有了（8）式与（9）式<br><img src="/images/RL/20.jpg" alt="进一步求解"><br>将（9）带入（8）中得（10）<br>将（8）带入（9）中得（11）<br>这样我们就可以利用（10）式来递归求解V函数，利用（11）式来递归求解q函数。<br>用一个图来理解一下递归求V函数的过程：<br><img src="/images/RL/21.jpg" alt="求V函数"><br>前半段表示当前状态下，当前行为下的价值，后半段是利用当前状态与当前行为推出下一步状态，并利用下一步状态的价值迭代求解。<strong>通过当前状态和决策函数policy来求解当前状态的价值的过程称为：Policy Evaluation</strong>   </p>
<h1 id="4-MDP预测与控制"><a href="#4-MDP预测与控制" class="headerlink" title="4.MDP预测与控制"></a>4.MDP预测与控制</h1><blockquote>
<p>预测（Prediction）和控制（Control）MDP的核心问题，预测问题是指给定一个MDP和Policy去计算价值函数；控制问题是寻找一个最佳的策略，输入是MDP，输出是最佳价值函数与最佳Policy。这两个问题都可以通过DP（动态规划）来求解。  </p>
</blockquote>
<h2 id="4-1-预测"><a href="#4-1-预测" class="headerlink" title="4.1 预测"></a>4.1 预测</h2><p><img src="/images/RL/23.jpg" alt="预测求解"><br>递归至收敛就完事了，由于已经给定了Policy，也可以当成一个MRP，改写成如下：<br><img src="/images/RL/24.jpg" alt="预测求解">   </p>
<p>来看一个栗子：Small Gridworld<br><img src="/images/RL/25.jpg" alt="Small Gridworld"><br>（1）左上角和右下角为终止状态，其余状态分别对应1至14，目的是到达终止状态。<br>（2）每个状态都是随机游走，即使是在边缘，例如状态4依然存在左走可能，但不会改变状态，即状态4往左走还是状态4，状态7往右走还是状态7。<br>（3）不使用折价因子（γ）<br>（4）每走一步会得到-1奖励，所以agent应该尽快到达终止状态。<br>我们可以<u><a href="https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html" target="_blank" rel="noopener">在线</a></u>看下这个例子的一个动态的迭代计算价值的过程。  </p>
<h2 id="4-2-控制"><a href="#4-2-控制" class="headerlink" title="4.2 控制"></a>4.2 控制</h2><p>最优状态价值（optimal state-value）函数定义如下：<br><img src="/images/RL/26.jpg" alt="最优状态价值函数"><br>其目的是在状态s下采取最优策略能够达到最大化的价值，而最优策略（optimal policy）定义如下：<br><img src="/images/RL/27.jpg" alt="最优策略"><br>即在状态s下能够达到最大化价值的策略。<br>当我们知道了一个MDP的最优状态价值函数的时候，我们称这个MDP解决了。<br>需要注意的是，只存在一个最优状态价值函数，但可能存在多个最优策略，因为有可能两种行为所得到的价值是相同的。  </p>
<p>所以MDP控制的核心就在于如何寻找最佳的Policy？<br><img src="/images/RL/28.jpg" alt="最佳策略"><br>选择最大化q函数的那个action就好了，所以如果我们知道了q函数，那么我们就能够通过最大化q函数选择最优策略。  </p>
<p>Policy Search<br>如果状态有限然后行为也是我们行为集合也是能知道的，我们可以直接穷举在所有状态下的策略。然后去计算一个最好的策略。但是效率很低，所以一般采取迭代法，具体分为两种：Policy Iteration和Value Iteration。  </p>
<h3 id="4-2-1-Policy-Iteration"><a href="#4-2-1-Policy-Iteration" class="headerlink" title="4.2.1 Policy Iteration"></a>4.2.1 Policy Iteration</h3><p>分为两步：  </p>
<ul>
<li>evalution：评估一个policy π，在当前的π上计算价值函数v，进一步可以得到q函数  </li>
<li>improvement：利用贪心的思想提升policy π的表现，极大化q函数 </li>
</ul>
<p><img src="/images/RL/29.jpg" alt="Policy Iteration"><br>例如现在有一个状态s，以及一个初始的Policy π，然后可以根据π得到一个a行为的分布，接着可以计算q函数，如下：<br><img src="/images/RL/30.jpg" alt="Policy Iteration"><br>再下一步，最大化这个q函数：<br><img src="/images/RL/31.jpg" alt="Policy Iteration"><br>直接让policy是选取最大化q函数的那个行为a，我们可以将这个过程看成一个Q-table，再Q-table的每一列去最大化q的值：<br><img src="/images/RL/32.jpg" alt="Policy Iteration">  </p>
<p>迭代停止过后，我们便能够得到最优策略，由此可以得到最优状态价值：<br><img src="/images/RL/33.jpg" alt="Policy Iteration">  </p>
<h3 id="4-2-2-Value-Iteration"><a href="#4-2-2-Value-Iteration" class="headerlink" title="4.2.2 Value Iteration"></a>4.2.2 Value Iteration</h3><p><img src="/images/RL/34.jpg" alt="Value Iteration"><br>直接迭代价值函数，不从Policy下手。<br>具体过程如下：<br><img src="/images/RL/35.jpg" alt="Value Iteration">   </p>
<h3 id="4-2-3-对比"><a href="#4-2-3-对比" class="headerlink" title="4.2.3 对比"></a>4.2.3 对比</h3><p>Policy Iteration分两步进行：Policy evaluation + Policy improvement<br>Value Iteration：不涉及policy，直接优化value function，但迭代收敛算出value function时，可以直接求得policy，也就是说policy是在最后抽取出的。  </p>

            </div>

            <!-- Post Comments -->
            

        </div>
        <!-- Copyright 版权 start -->
                <div id="copyright">
            <ul>
                <li>&copy;2020 北望你的安. 版权所有</li>
            </ul>
            
                <span id="busuanzi_container_site_pv">本站总访问量<span id="busuanzi_value_site_pv"></span>次，</span>
				<span id="busuanzi_container_site_uv"> 访客数 <span id="busuanzi_value_site_uv"></span> 人. </span>
			
			<br>
			<span>友情链接：<a href='http://www.demilab.cn' target='_blank'>DEMI实验室</a>&nbsp;&nbsp;&nbsp;<a href='http://zd11024.cn/' target='_blank'>ZD</a></span>
        </div>
    </div>
</body>



 	
</html>
